Exercise: Random Binary Search Trees

Implement a treap from a sorted array.

We'll cover the following

Task#

Design and implement an algorithm that constructs a Treap from a sorted array, a, of n elements. This method should run in O(n)O(n) worst-case time and should construct a Treap that is indistinguishable from one in which the elements of a were added one at a time using the add(x) method.

Sample input

The sample input will be as follows:

1
2
3
4
5

Expected output

The expected output will be as follows:

Tree contents:
1 2 3 4 5 6 
Tree contents after removing 4:
1 2 3 5 6 

Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.

Good luck!

svg viewer

Note: You must implement the method addall() and addallrecursive() in the below code starting at line 19.

main.py
arrayqueue.py
binarytree.py
base.py
utils.py
binarysearchtree.py
Task to implement addall() and addallrecursive() method

Discussion on Random Binary Search Trees

Solution: Random Binary Search Trees